/**
 * https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/submissions/568499256/
 * 902. 最大为 N 的数字组合
 * difficulty 2024.09.27
 * 数位dp
 */

class Solution {
public:
    int rep;
    int sum=0;
    int m;
    int num=0;
    int t;
    void dfs(vector<string>& digits,int n,int d){
        for(int i=0;i<m;++i){
            int g=stoi(digits[i]);
            if(n<num)
            dfs(digits,n+1,d*10+g);
            else{
                if(d<rep)
                    sum++;
                else if(d==rep&&t>=g)
                    sum++;
                else
                    return;
            }
        }
    }
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        m=digits.size();
        rep=n/10;
        t=n%10;
        while(n/10){
            n/=10;
            num++;
        }
        if(num==0){
           for(auto x:digits){
            if(stoi(x)>n)
            break;
            sum++;
        }
        return sum;
        }
        int g=m;
        for(int i=0;i<num;++i){
            sum+=g;
            g*=m;
        }
        g/=m;
        int i=0;
        for(;i<m;++i){
            if(stoi(digits[i])>=n)
            break;
            sum+=g;
        }
        if(i<m&&stoi(digits[i])==n)
        dfs(digits,1,stoi(digits[i]));
        return sum; 
    }
};